/*
 * queue.cpp
 *
 *  Created on: Jul 9, 2012
 *      Author: jh238d
 */

#include <queue>
#include <iostream>
using namespace std;

/*push/pop/getmin in queue O(1)*/
struct QueueGetMin{
	queue<int> q;
	deque<int> minQ;

	void push(int data){
		q.push(data);
		if(minQ.empty()||minQ.front()>data){
			while(!minQ.empty())
				minQ.pop_back();
			minQ.push_front(data);
		}else{
			while(minQ.back()>data)
				minQ.pop_back();
			minQ.push_back(data);
		}
	}

	bool pop(){
		if(q.empty()) return false;
		int data = q.front();
		q.pop();
		if(data==minQ.front())
			minQ.pop_front();
		return true;
	}

	bool getMin(int &min){
		if(q.empty()) return false;
		else{
			min = minQ.front();
		}
		return true;
	}
};
